package redis;

import java.util.BitSet;
import java.util.Random;

public class CuckooFilter {
    private static final int MAX_KICKS = 500; // 最大踢出次数
    private static final int DEFAULT_NUM_BUCKETS = 1024; // 默认桶数量
    private static final int DEFAULT_BUCKET_SIZE = 4; // 默认每个桶的大小

    private BitSet[] buckets; // 存储指纹的桶数组
    private int numBuckets; // 桶的数量
    private int bucketSize; // 每个桶的大小
    private int numItems; // 当前过滤器中存储的元素数量

    // 统计信息
    private long insertCount = 0; // 插入操作次数
    private long queryCount = 0; // 查询操作次数
    private long deleteCount = 0; // 删除操作次数
    private long insertSuccess = 0; // 插入成功次数
    private long querySuccess = 0; // 查询成功次数
    private long deleteSuccess = 0; // 删除成功次数

    /**
     * 构造函数，初始化布谷鸟过滤器。
     *
     * @param numBuckets 桶的数量（可选，默认为 DEFAULT_NUM_BUCKETS）
     * @param bucketSize 每个桶的大小（可选，默认为 DEFAULT_BUCKET_SIZE）
     */
    public CuckooFilter(int numBuckets, int bucketSize) {
        this.numBuckets = numBuckets;
        this.bucketSize = bucketSize;
        this.buckets = new BitSet[numBuckets];
        for (int i = 0; i < numBuckets; i++) {
            buckets[i] = new BitSet(bucketSize);
        }
        this.numItems = 0;
    }

    public CuckooFilter() {
        this(DEFAULT_NUM_BUCKETS, DEFAULT_BUCKET_SIZE);
    }

    /**
     * 检查一个元素是否存在于布谷鸟过滤器中。
     *
     * @param item 要检查的元素
     * @return 如果元素存在返回 true，否则返回 false
     */
    public boolean contains(String item) {
        queryCount++;
        int fingerprint = getFingerprint(item);
        int bucket1 = getBucket(item);
        int bucket2 = getAltBucket(bucket1, fingerprint);
        boolean exists = buckets[bucket1].get(fingerprint) || buckets[bucket2].get(fingerprint);
        if (exists) {
            querySuccess++;
        }
        return exists;
    }

    /**
     * 向布谷鸟过滤器中插入一个元素。
     *
     * @param item 要插入的元素
     * @return 如果插入成功返回 true，否则返回 false
     */
    public boolean insert(String item) {
        insertCount++;
        if (contains(item)) {
            return false; // 如果元素已经存在，则直接返回 false
        }

        int fingerprint = getFingerprint(item);
        int bucket1 = getBucket(item);
        int bucket2 = getAltBucket(bucket1, fingerprint);

        if (buckets[bucket1].cardinality() < bucketSize) {
            buckets[bucket1].set(fingerprint);
            numItems++;
            insertSuccess++;
            return true;
        } else if (buckets[bucket2].cardinality() < bucketSize) {
            buckets[bucket2].set(fingerprint);
            numItems++;
            insertSuccess++;
            return true;
        } else {
            Random random = new Random();
            int bucket = random.nextBoolean() ? bucket1 : bucket2;
            int i = 0;
            while (i < MAX_KICKS) {
                int evictedFingerprint = random.nextInt(bucketSize);
                if (!buckets[bucket].get(evictedFingerprint)) {
                    buckets[bucket].set(evictedFingerprint);
                    String evictedItem = getItem(bucket, evictedFingerprint);
                    if (insert(evictedItem)) {
                        insertSuccess++;
                        return true;
                    }
                }
                i++;
            }
            rehash();
            return insert(item);
        }
    }

    /**
     * 从布谷鸟过滤器中删除一个元素。
     *
     * @param item 要删除的元素
     * @return 如果删除成功返回 true，否则返回 false
     */
    public boolean delete(String item) {
        deleteCount++;
        int fingerprint = getFingerprint(item);
        int bucket1 = getBucket(item);
        int bucket2 = getAltBucket(bucket1, fingerprint);

        if (buckets[bucket1].get(fingerprint)) {
            buckets[bucket1].clear(fingerprint);
            numItems--;
            deleteSuccess++;
            return true;
        } else if (buckets[bucket2].get(fingerprint)) {
            buckets[bucket2].clear(fingerprint);
            numItems--;
            deleteSuccess++;
            return true;
        }
        return false;
    }

    /**
     * 计算元素的指纹。
     *
     * @param item 要计算指纹的元素
     * @return 指纹值
     */
    private int getFingerprint(String item) {
        return Math.abs(item.hashCode()) % bucketSize;
    }

    /**
     * 计算元素的第一个桶位置。
     *
     * @param item 要计算桶位置的元素
     * @return 第一个桶的位置
     */
    private int getBucket(String item) {
        return Math.abs(item.hashCode()) % numBuckets;
    }

    /**
     * 计算元素的第二个桶位置。
     *
     * @param bucket 第一个桶的位置
     * @param fingerprint 元素的指纹
     * @return 第二个桶的位置
     */
    private int getAltBucket(int bucket, int fingerprint) {
        return bucket ^ (fingerprint % numBuckets);
    }

    /**
     * 根据桶位置和指纹构造一个虚拟的元素，用于递归插入。
     *
     * @param bucketIndex 桶的位置
     * @param fingerprint 指纹
     * @return 虚拟的元素
     */
    private String getItem(int bucketIndex, int fingerprint) {
        return bucketIndex + ":" + fingerprint;
    }

    /**
     * 对布谷鸟过滤器进行 rehash 操作，扩大桶的数量。
     */
    private void rehash() {
        int newNumBuckets = numBuckets * 2;
        BitSet[] newBuckets = new BitSet[newNumBuckets];
        for (int i = 0; i < newNumBuckets; i++) {
            newBuckets[i] = new BitSet(bucketSize);
        }

        for (int i = 0; i < numBuckets; i++) {
            BitSet bucket = buckets[i];
            for (int j = 0; j < bucketSize; j++) {
                if (bucket.get(j)) {
                    String item = getItem(i, j);
                    int newBucket = getBucket(item);
                    newBuckets[newBucket].set(getFingerprint(item));
                }
            }
        }

        buckets = newBuckets;
        numBuckets = newNumBuckets;
    }

    /**
     * 获取布谷鸟过滤器的统计信息。
     *
     * @return 包含插入、查询、删除等操作的统计信息
     */
    public String getStatistics() {
        return String.format(
                "Insert Count: %d, Insert Success: %d%n" +
                        "Query Count: %d, Query Success: %d%n" +
                        "Delete Count: %d, Delete Success: %d%n" +
                        "Current Items: %d, Buckets: %d, Bucket Size: %d",
                insertCount, insertSuccess,
                queryCount, querySuccess,
                deleteCount, deleteSuccess,
                numItems, numBuckets, bucketSize
        );
    }

//    public static void main(String[] args) {
//        CuckooFilter filter = new CuckooFilter();
//        filter.insert("item1");
//        filter.insert("item2");
//        filter.insert("item3");
//
//        System.out.println("Contains item1: " + filter.contains("item1")); // true
//        System.out.println("Contains item4: " + filter.contains("item4")); // false
//
//        filter.delete("item1");
//        System.out.println("Contains item1 after delete: " + filter.contains("item1")); // false
//
//        System.out.println(filter.getStatistics());
//    }
}